1. Field of the Invention
The present invention relates generally to methods and circuits for computing and, more particularly, to methods and circuits for computing the product of two elements in a finite field or the inverse of an element in a finite field.
2. Description of the Related Art
Multiplication over large finite fields, also known as Galois fields, is used in the implementation of certain cryptographic protocols based on a theory of elliptic curves over Galois fields. These cryptographic protocols are highly computationally intensive and therefore consume a significant level of computational resources in order to perform Galois field arithmetic. Consequently, any reduction in the number of operations required for Galois field arithmetic will have a significant impact on the overall consumption of computational resources.
Generally speaking, a field is a number system with addition, subtraction, multiplication and division. The operations on the elements of the field should be associative, distributive and commutative. Therefore, there should be an element 0, where 0+x=x, and an element 1, where 1*x=x. In addition, for every x, there is a (xe2x88x92x), where x+(xe2x88x92x)=0. Further, for every value of x that is not 0, there is an inverse (1/x) where x*(1/x)=1.
Some well-known examples of fields are the real numbers, the rational numbers and the complex numbers. Each of these sets have an infinite number of elements and are therefore infinite fields.
Finite fields have a finite number of elements. As an example, when p is a prime number, a finite field GF(p) is a field with p elements. The elements of the field GF(p) may be taken to be 0, 1, . . . , pxe2x88x921. Elements of the field may be added, subtracted and multiplied, but the resulting number is reduced modulo the value of p (mod p) at the end of the computation. See Chapter 4 of MacWilliams and Sloane, The Theory of Error-Correcting Codes, North Holland, 1977.
The smallest of all fields is the finite field GF(2), which is a finite field having two elements: 0 and 1. The elements may be added, subtracted, multiplied and divided. However, 1+1=0, because the modulo equivalent of the result of the addition, 2, is 0, i.e. 1+1=2 mod 2=0. Similarly, 0xe2x88x921=1, because the result of the subtraction, (xe2x88x921), is reduced modulo the value of p, which is 2, the result of the subtraction is a modulo 1, i.e. 0xe2x88x921=(xe2x88x921) mod 2=1.
Another type of finite field is GF(2n), a field with 2n elements. GF(2n) is an n-th degree extension of GF(2).
The finite field GF(2n) is a vector space of dimension n over GF(2). As such, it can be represented using any basis of n linearly independent elements of GF(2n) over the binary field GF(2). Therefore, elements of GF(2n) are represented by binary vectors of length n. Field addition is realized in all bases by a bit-wise exclusive OR (XOR) operation, whereas the structure of field multiplication is determined by the choice of basis for the representation.
There are several representations of extension fields GF(2n) that lend themselves to efficient arithmetic implementation over the binary field GF(2).
Two families of bases are commonly used to represent the field GF(2n): standard (or polynomial) representation and normal basis (NB) representation. For certain values of n, a special case of the letter is called optimal normal basis (ONB).
In standard polynomial representation, the basis elements have the form 1,xcfx89,xcfx892, . . . , xcfx89nxe2x88x921, where xcfx89 is a root in GF(2n) of an irreducible polynomial P(x) of degree n over GF(2). In an equivalent interpretation of this representation, the elements of GF(2n) are polynomials of degree at most nxe2x88x921 over GF(2), and arithmetic is carried out modulo an irreducible polynomial P(x) of degree n over GF(2).
In ONB representation, the basis elements have the form (xcex1, xcex12, . . . , xcex12xc2x7xe2x80x2) for a certain element xcex1 xcex5 GF(2n). This defines a normal basis. In addition, if for all 0xe2x89xa6ixe2x89xa0jxe2x89xa6nxe2x88x921 there exists k, l such that,
xcex1(2xc2x7xc2x72xe2x80x2)=xcex12xc2x7+xcex12xe2x80x2, 
then the basis is called optimal. The element xcex1 is called the generator of the basis. Optimal normal bases exist for an infinite subset of values of n defined later on.
When the polynomial P(x) is sparse, the standard representation lends itself to efficient software implementations of the field arithmetic. In the software execution context, there are efficient implementations for polynomial multiplication and inversion. On the other hand, the ONB representation typically allows for more efficient hardware implementations of field multiplication. See Ch. 5 of Menezes et al, Applications of Finite Fields, Kluwer, Boston, 1993 and Omura and Massey (U.S. Pat. No. 4,587,627). Inversion, however, remains a difficult operation in the hardware execution context. Addition is typically easy to accomplish in either execution context.
Large finite fields are the basis of many modern cryptographic algorithms, e.g. elliptic curve cryptography. In these applications, n is typically on the order of 100 which, using some conventional algorithms, can require thousands of operations in order to perform a computation. The field arithmetic therefore becomes a computational bottleneck and use of the most efficient implementations available is important to reducing the overhead required to perform cryptographic operations. On the other hand, the explosive development of the Internet is expected to make the use of encryption become widespread, and will require hardware and software implementations to interoperate and use common representations.
Accordingly, the need remains for a method for making use of efficient algorithms to perform arithmetic operations in large finite fields.
It is, therefore, an object of the invention to reduce execution overhead by using the most efficient algorithms available in a given execution content to perform finite field computation.
An embodiment of a method for performing efficient arithmetic in a finite field, according to the present invention, involves receiving a first operand having a first representation format and permuting the format of the first operand from the first representation format to an alternative representation format. The method also involves receiving a second operand having the first representation format and permuting the second operand from the first representation format to the alternative representation format. Then a result having the alternative representation format is generated by performing a selected arithmetic operation on the first and second operands. The format of the result is then permuted from the alternative representation format to the first representation format.
Another embodiment of a method for performing an inversion operation in a finite field, according to the present invention, includes receiving an operand having an optimal normal basis (ONB) format, permuting the format of the operand to an alternative representation format, and generating a result having the alternative representation format by inverting the first operand.
Yet another embodiment of a method, according to the present invention, for performing an arithmetic operation on first and second n-length vectors having a first representation format in a finite field GF(2n) in a predetermined execution context includes selecting an efficient algorithm for the arithmetic operation based upon the predetermined execution context, selecting an execution representation format based upon the selected efficient algorithm, where the execution representation format is one of the first representation format and a second representation format, permuting the first and second vectors from the first representation format to the second representation format when the selected execution representation format is the second representation format, and performing the arithmetic operation on the first and second vectors to obtain a result having the selected execution representation format.
Still another embodiment of a method for performing an arithmetic operation on an n-length vector having a first representation format in a finite field GF(2n) in a predetermined execution context, according to the present invention, involves selecting an efficient algorithm for the arithmetic operation based upon the predetermined execution context, selecting an execution representation format based upon the selected efficient algorithm, where the execution representation format is one of the first representation format and a second representation format, permuting the vector from the first representation format to the second representation format when the selected execution representation format is the second representation format, and performing the arithmetic operation on the vector to obtain a result having the selected execution representation format.
Yet another embodiment of an apparatus for performing an arithmetic operation in a finite field, according to the present invention, is composed of a first buffer configured to receive and store a first input operand having a first representation format, a first format converter configured to convert the first input operand to a first converted operand having a second representation format, and a second buffer configured to receive and store the first converted operand. A functional unit is configured to receive the first converted operand from the second buffer and perform the arithmetic operation on the first converted operand in order to generate a first result having the second representation format. The apparatus also includes a third buffer configured to receive and store the first result, a second format converter configured to convert the first to a second result having the first representation format, and a fourth buffer configured to receive and store the second result.
An embodiment of a computer readable medium having stored therein a plurality of routines, according to the present invention, includes a first routine configured to convert a first operand having a first representation format to a second operand having a second representation format, a second routine configured to perform a first arithmetic operation on the second operand in order to obtain a first result having the second representation format, and a third routine configured to convert the first result to a second result having the first representation format.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of several embodiments of the invention which proceeds with reference to the accompany drawings.